package com.atguigu.search;

public class BinarySearch {

    private BinarySearch() {
    }


    public static <E extends Comparable<E>> int search(E[] data, E target) {
        int l = 0, r = data.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (data[mid].compareTo(target) == 0) {
                return mid;
            } else if (data[mid].compareTo(target) > 0) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }

    public static <E extends Comparable<E>> int searchR(E[] data, E target) {
        return searchR(data, 0, data.length - 1, target);
    }

    //在data[l,r]中递归查找target
    private static <E extends Comparable<E>> int searchR(E[] data, int l, int r, E target) {
        if (l > r) {
            return -1;
        }
        int mid = l + (r - l) / 2;
        if (data[mid].compareTo(target) == 0) {
            return mid;
        } else if (data[mid].compareTo(target) > 0) {
            return searchR(data, l, mid - 1, target);
        } else {
            return searchR(data, mid + 1, r, target);
        }
    }

    //查找大于target的最小值的索引
    public static <E extends Comparable<E>> int upper(E[] data, E target) {
        int r = data.length, l = 0;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (data[mid].compareTo(target) > 0) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }

    //查找大于等于target的最小值索引
    public static <E extends Comparable<E>> int lower_ceil(E[] data, E target) {
        int l = 0, r = data.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (data[mid].compareTo(target) < 0) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }

    //查找小于target的最大值的索引
    public static <E extends Comparable<E>> int lower(E[] data, E target) {
        int l = -1, r = data.length - 1;
        while (l < r) {
            int mid = l + (r - l + 1) / 2;//[1,1] target=2;可能出现死循环,向上取整，而不是向下取整
            if (data[mid].compareTo(target) >= 0) {
                r = mid - 1;
            } else {
                l = mid;
            }
        }
        return l;
    }

    public static void main(String[] args) {
        Integer[] data = {1, 1, 3, 3, 4, 4, 4};
        for (int i = 0; i <= 6; i++) {
            System.out.print(lower(data, i) + " ");
        }

    }
}
